package 牛客.链表;

import 剑指offer.ListNode;

import java.util.HashSet;
import java.util.Set;

public class BM7链表中环的入口结点 {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //快慢指针
        //先找到相遇点，
        //在让快指针或慢指针任意一个回到起始点，两个指针各走一步，再次相遇点即为环的入口点
        if(pHead==null || pHead.next==null) {
            return null;
        }
        ListNode slow=pHead;
        ListNode fast=pHead;
        while(fast!=null && fast.next!=null) {
            slow=slow.next;
            fast=fast.next.next;
            if(fast==slow) {
                //找到相遇点，则结束循环
                break;
            }
        }

        if(fast==null || fast.next==null) {
            //没有环
            return null;
        }

        //有环，找换的入口点
        fast=pHead;
        while(fast!=slow) {
            //slow从相遇点到换入口的距离 == fast从起始点到换入口点的距离
            //数学证明
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }

    public ListNode EntryNodeOfLoop1(ListNode pHead) {
        //哈希表
        if (pHead==null || pHead.next==null) {
            return null;
        }
        Set<ListNode> set=new HashSet<>();
        ListNode cur=pHead;
        while (cur!=null) {
            if (set.contains(cur)) {
                return cur;
            }else {
                set.add(cur);
                cur=cur.next;
            }
        }

        return null;//没有环
    }
}
